package com.czh.problem.zuochenyun;

/**
 * @author chenzhihua
 * @Date 2024/3/12
 */
public class LikouTest {
    public static void main(String[] args) {
        // 绳子覆盖最多的点数
//        int[] arr = new int[]{1, 4, 5, 6, 9, 10, 12, 17};
//        System.out.println(maxPoint(arr, 4));
        //G和B的最少交换次数
//        System.out.println(minStep("BBGGBBGBG"));

        int[] arr = new int[]{1, 2, 3, 4, 5};
        int target = 3;
        System.out.println(findTargetSumWays(arr, target));
    }

    //========================左程云====================================/
    // 绳子覆盖最多的点数--给定一个有序数组arr代码在x轴上的点，给定一个正数k，代表绳子的长度，求绳子最多压中几个点
    public static int maxPoint(int[] arr, int k) {
        // 二分法n*logn
        //双指针n
        // left左指针，right最大压中点的位置，max最大压中点
        int left = 0, right = 0, max = 0;
        int length = arr.length;
        while (left < length) {
            // 计算right最大移动距离
            while (right < length && arr[right] - arr[left] <= k) {
                right++;
            }
            max = Math.max(max, right - (left++));
        }
        return max;
    }

    // 一个数组中只有G和B,想让G都放在左侧，B都在右侧，G和B可以调换位置，但是只能在相邻字符间进行交换返回最少需要交换几次
    public static int minStep(String s) {
        if (s == null || "".equals(s)) {
            return 0;
        }
        // gi:遍历的第n个G的位置,bi:遍历的第n个B的位置，gc,bc：移动的次数
        int gi = 0, gc = 0, bi = 0, bc = 0;
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            if (charArray[i] == 'G') {
                // 求G在左边的最小交换次数
                gc += i - gi;
                gi++;
            } else {
                // 求B在左边的最小交换次数
                bc += i - bi;
                bi++;
            }
        }
        return Math.min(gc, bc);
    }

    // 给定一个二维数据maxtrix，你可以从任何位置出发，走上下左右四个方向，返回能走出来的最长的递增链长度

    // 给定一个数组arr，你可以决定在每个数字之前决定+或者-但是必须所有数字都参与，在给定一个target，请问最后算出target的方法数时多少
    public static int findTargetSumWays(int[] arr, int target) {
        // 1. 递归实现
        return process1(arr, 0, target);
        // 2. 动态规划 TODO
    }

    private static int process1(int[] arr, int index, int target) {
        if (index == arr.length) {
            // 遍历了所有数，如果得出的值和target一样则说明有解，否则没解
            return target == 0 ? 1 : 0;
        }
        // 还有数，当前数加后面那个数或者减后面那个数
        return process1(arr, index + 1, target - arr[index]) + process1(arr, index + 1, target + arr[index]);
    }
}
